
//删除多余字符得到字典序最小的字符串

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string method(const string& str) {
        if (str.size() == 0) { return str;}
        string res;

        // 遍历str 生成次数统计表
        vector<int> count(26, 0);
        for (auto c : str) {
            count[c - 'a']++;
        }

        int strIndex = 0;

        // 遍历str 逐个减少统计表的数量 
        for (int i = 0; i < str.size(); i++) {

            // 数量为0时该字符需加入res
            if (--count[str[i] - 'a'] == 0) {
                // 查询在str[i]之前在字符串中出现过的字典序小于 str[i]的字母 
                //并将其数量赋值为-1 然后形成str[i]的前段
                for (int j = strIndex; j < i; j++) {
                    // 字典序小于str[i] && 出现过
                    if (str[j] < str[i] && count[str[j] - 'a'] > 0) {
                        count[str[j] - 'a'] = -1;
                    }

                }
                strIndex = i;
                // 将位于str[i]前的出现的字符形成字典序 并归零
                for (int j = 0; j < str[i] - 'a'; j++) {
                    if (count[j] == -1) {
                        res += (j + 'a');
                        count[j] = 0;
                    }
                }
                res += str[i];
            }
        }

        return res;
    }
};

int main() {
    string str = "dbcacbca";
    Solution solu;
    cout << solu.method(str);
    return 0;
}